1. Field of the Invention
This invention relates to data mining, and more particularly to apparatus and processes for mining sequential patterns in directed graphs such as computer-program control flow graphs.
2. Background of the Invention
Identifying performance bottlenecks is one of the most important (and difficult) tasks a software developer faces when trying to improve the efficiency of program code. This is because a large amount of time is typically spent executing a relatively small number of execution patterns (instructions, sequences of instructions, etc.) within the code. This is true for even large software systems such as web applications. Consequently, it is important for software developers to be able to identify execution patterns that may be performance bottlenecks so that these executions patterns can be optimized. Unfortunately, finding these execution patterns can be challenging.
At a very low level, performance bottlenecks in a program can take a number of forms. For example, a performance bottleneck may occur as a result of a contextual situation which could potentially be solved by optimizing the compiler. A bottleneck may also be the result of poor code generation by the compiler. In either case, an engineer may identify these bottlenecks by examining performance data in the form of hardware profiles. The information in hardware profiles varies from architecture to architecture, but usually includes such information as instruction and data cache misses, and other low-level information. A hardware profile by nature is aggregated, which is to say that if one section of code is visited multiple times, the data from each visit will be grouped together.
More often, low level performance issues are identified through manual observation. For example, a compiler engineer may manually examine a hardware profile in an attempt to identify patterns which are indicative of a performance bottleneck. The engineer may then devise a solution to increase the efficiency of the bottleneck. This process is typically slow and heavily reliant on the intuition of the compiler engineer.
In view of the foregoing, what are needed are apparatus and methods to more easily identify execution patterns that are potential performance bottlenecks in program code. Ideally, such apparatus and methods could leverage and improve upon existing data mining techniques for finding sequential patterns. Such apparatus and methods will ideally allow software developers to direct resources to optimizing the executions patterns that represent performance bottlenecks. Yet further needed are apparatus and methods to find sequential patterns in any method or process that can be represented as a directed graph having branches, join points, and/or cycles.